#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

template <typename KeyType>
class ScapegoatTree {
public:
	struct Node {
		KeyType key;
		int size;
		Node* left;
		Node* right;

		Node(const KeyType& k) : key(k), size(1), left(nullptr), right(nullptr) {}
	};

	ScapegoatTree(double alpha = 0.75) : root_(nullptr), alpha_(alpha) {}

	~ScapegoatTree() {
		std::vector<Node*> stack;
		if (root_) stack.push_back(root_);
		while (!stack.empty()) {
			Node* node = stack.back();
			stack.pop_back();
			if (node->left) stack.push_back(node->left);
			if (node->right) stack.push_back(node->right);
			delete node;
		}
	}

	bool Insert(const KeyType& key) {
		Node* node = root_;
		Node* parent = nullptr;
		std::vector<Node*> path;
		while (node) {
			parent = node;
			path.push_back(node);
			node->size++;
			if (key < node->key) {
				node = node->left;
			} else if (node->key < key) {
				node = node->right;
			} else {
				return false;
			}
		}
		node = new Node(key);
		if (!parent) {
			root_ = node;
		} else if (key < parent->key) {
			parent->left = node;
		} else {
			parent->right = node;
		}
		path.push_back(node);
		if (ComputeAlpha(path) > alpha_) {
			Rebuild(path);
		}
		return true;
	}

	bool Delete(const KeyType& key) {
		Node* node = root_;
		Node* parent = nullptr;
		std::vector<Node*> path;
		while (node) {
			path.push_back(node);
			if (key < node->key) {
				parent = node;
				node = node->left;
			} else if (node->key < key) {
				parent = node;
				node = node->right;
			} else {
				break;
			}
		}
		if (!node) {
			return false;
		}
		if (node->left && node->right) {
			Node* min_node = node->right;
			while (min_node->left) {
				min_node->size--;
				path.push_back(min_node);
				min_node = min_node->left;
			}
			node->key = min_node->key;
			node = min_node;
			parent = path.empty() ? nullptr : path.back();
		}
		Node* child = node->left ? node->left : node->right;
		if (!parent) {
			root_ = child;
		} else if (node == parent->left) {
			parent->left = child;
		} else {
			parent->right = child;
		}
		while (!path.empty()) {
			Node* cur_node = path.back();
			path.pop_back();
			cur_node->size--;
			if (ComputeAlpha(path) > alpha_) {
				Rebuild(path);
			}
		}
		delete node;
		return true;
	}

	bool Search(const KeyType& key) const {
		Node* node = root_;
		while (node) {
			if (key < node->key) {
				node = node->left;
			} else if (node->key < key) {
				node = node->right;
			} else {
				return true;
			}
		}
		return false;
	}

	int Rank(const KeyType& key) const {
		Node* node = root_;
		int rank = 0;
		while (node) {
			if (key < node->key) {
				node = node->left;
			} else {
				rank += (node->left ? node->left->size : 0) + 1;
				if (node->key < key) {
					node = node->right;
				} else {
					break;
				}
			}
		}
		return rank;
	}

	KeyType Select(int rank) const {
		Node* node = root_;
		while (node) {
			int left_size = node->left ? node->left->size : 0;
			if (rank < left_size) {
				node = node->left;
			} else if (rank == left_size) {
				break;
			} else {
				rank -= left_size + 1;
				node = node->right;
			}
		}
		return node->key;
	}

private:
	Node* root_;
	double alpha_;

	double ComputeAlpha(const std::vector<Node*>& path) const {
		int size = path.back()->size;
		int depth = path.size();
		double log_alpha = std::log(1.0 / alpha_);
		double log_size = std::log(size);
		return log_size / log_alpha / depth;
	}

	void Rebuild(const std::vector<Node*>& path) {
		Node* node = path.back();
		std::vector<Node*> nodes;
		Flatten(node, nodes);
		int size = nodes.size();
		int mid = size / 2;
		root_ = nodes[mid];
		root_->size = size;
		root_->left = Build(nodes, 0, mid - 1);
		root_->right = Build(nodes, mid + 1, size - 1);
	}

	void Flatten(Node* node, std::vector<Node*>& nodes) const {
		if (node->left) Flatten(node->left, nodes);
		nodes.push_back(node);
		if (node->right) Flatten(node->right, nodes);
	}

	Node* Build(const std::vector<Node*>& nodes, int left, int right) {
		if (left > right) {
			return nullptr;
		}
		int mid = (left + right) / 2;
		Node* node = nodes[mid];
		node->left = Build(nodes, left, mid - 1);
		node->right = Build(nodes, mid + 1, right);
		node->size = 1;
		if (node->left) node->size += node->left->size;
		if (node->right) node->size += node->right->size;
		return node;
	}
};
